package cn.zifangsky.dp.questions;

import org.junit.Test;

/**
 * 机器人达到指定位置方法数
 * <p>假设有排成一行的N个位置，记为1～N，N一定大于或等于2。
 * 开始时机器人在其中的M位置上（M一定是1～N中的一个），机器人可以往左走或者往右走，
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到N-1位置。
 * 规定机器人必须走K步，最终能来到P位置（P也一定是1～N中的一个）的方法有多少种。给定四个参数N、M、K、P，返回方法数。</p>
 *
 * <p>示例：</p>
 * <p><b>N=5,M=2,K=3,P=3</b></p>
 * <p>上面的参数代表所有位置为12345。机器人最开始在2位置上，必须经过3步，最后到达3位置。</p>
 *
 * @author zifangsky
 * @date 2020/5/25
 * @since 1.0.0
 */
public class Problem_005_RobotWalk {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int n = 5;
        int m = 2;
        int k = 3;
        int p = 3;
//        int n = 7;
//        int m = 4;
//        int k = 9;
//        int p = 5;

        //1. 测试方法一
        System.out.println(solution1(n, m, k, p));
        //2. 测试方法二
        System.out.println(solution2(n, m, k, p));
        //3. 测试方法三
        System.out.println(solution3(n, m, k, p));
    }


    /**
     * 解法一：使用暴力递归方式求解
     *
     * @param n 位置总数
     * @param m 当前位置
     * @param k 行走步数
     * @param p 目的位置
     */
    private int solution1(int n, int m, int k, int p){
        if(n < 2 || m < 1 || m > n || k < 1 || p < 1 || p > n){
            return 0;
        }

        return walk(n, m, k, p);
    }

    /**
     * 机器人行走方式的抽象
     *
     * @param n 位置总数
     * @param cur 当前位置
     * @param rest 剩余步数
     * @param p 目的位置
     */
    private int walk(int n, int cur, int rest, int p){
        //当剩余步数走完时返回结果
        if(rest == 0){
            return (cur == p ? 1 : 0);
        }

        //当机器人在最左边时，只能向右移动
        if(cur == 1){
            return walk(n, 2, rest - 1, p);
        }

        //当机器人在最右边时，只能向左移动
        if(cur == n){
            return walk(n, n - 1, rest - 1, p);
        }

        //其他位置，既可以往左边移动，又可以往右边移动
        return walk(n, cur - 1, rest - 1, p) + walk(n, cur + 1, rest - 1, p);
    }


    /**
     * 解法二：将问题转化为dp求解（算法思路类似于“矩阵的最小路径和”问题的求解）
     * <p>以机器人可能到达的位置为横坐标，剩余步数为纵坐标，于是这个问题可以转化为下面这样的二维数组：</p>
     *
     *     <table>
     *         <tr>
     *             <th>rest\current</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th>
     *         </tr>
     *         <tr>
     *             <th>2</th><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td>
     *         </tr>
     *         <tr>
     *             <th>1</th><td>0</td><td>2</td><td>0</td><td>1</td><td>0</td>
     *         </tr>
     *         <tr>
     *             <th>0</th><td>2</td><td>0</td><td>3</td><td>0</td><td>1</td>
     *         </tr>
     *     </table>
     *
     * @param n 位置总数
     * @param m 当前位置
     * @param k 行走步数
     * @param p 目的位置
     */
    private int solution2(int n, int m, int k, int p){
        if(n < 2 || m < 1 || m > n || k < 1 || p < 1 || p > n){
            return 0;
        }

        int[][] dp = new int[k][n];

        //1. 根据机器人所在当前位置，给数组第一行赋值
        //1.1 当机器人在最左边时，给位置2赋值
        if(m == 1){
            dp[0][2-1] = 1;
        }
        //1.2 当机器人在最右边时，给位置n-1赋值
        else if(m == n){
            dp[0][n-1-1] = 1;
        }
        //1.3 其他情况给位置m-1和m+1赋值
        else{
            dp[0][m-1-1] = 1;
            dp[0][m+1-1] = 1;
        }

        //2. 循环给其他行的位置赋值
        for(int i = 1; i < k; i++){
            for(int j = 0; j < n; j++){
                if(j == 0){
                    dp[i][j] = dp[i-1][j+1];
                }else if(j == (n - 1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
                }
            }
        }

        //3. 返回达到目的位置的行走方法数
        return dp[k-1][p-1];
    }


    /**
     * 解法三：
     * <p>解法三的思路跟解法二一致，但是还可以压缩空间，使用一个一维数组存储“还剩下rest步时到达每一个位置的走法个数”</p>
     *
     * @param n 位置总数
     * @param m 当前位置
     * @param k 行走步数
     * @param p 目的位置
     */
    private int solution3(int n, int m, int k, int p){
        if(n < 2 || m < 1 || m > n || k < 1 || p < 1 || p > n){
            return 0;
        }

        int[] dp = new int[n];

        //1. 根据机器人所在当前位置，给数组赋予初值
        //1.1 当机器人在最左边时，给位置2赋值
        if(m == 1){
            dp[2-1] = 1;
        }
        //1.2 当机器人在最右边时，给位置n-1赋值
        else if(m == n){
            dp[n-1-1] = 1;
        }
        //1.3 其他情况给位置m-1和m+1赋值
        else{
            dp[m-1-1] = 1;
            dp[m+1-1] = 1;
        }

        //2. 循环给其他行的位置赋值
        for(int i = 1; i < k; i++){
            //需要提前存储左上角的值，防止在循环过程中被覆盖
            int preVal = dp[0];
            for(int j = 0; j < n; j++){
                //被覆盖之前的当前位置的值
                int curVal = dp[j];

                if(j == 0){
                    dp[j] = dp[j+1];
                }else if(j == (n - 1)){
                    dp[j] = preVal;
                }else{
                    dp[j] = preVal + dp[j+1];
                }

                preVal = curVal;
            }
        }

        //3. 返回达到目的位置的行走方法数
        return dp[p-1];
    }
}
